/*
 * File:   main.cpp
 * Author: bashao
 *
 * Created on July 17, 2011, 2:34 AM
 */

#include <cstdlib>
#include <gmpxx.h>
#include <map>
using namespace std;

/*
 *
 */

map<int, map<int, mpz_t*> > cache;

mpz_t* get(int n, int v) {
    return cache[n][v];
}

void put(int n, int v, mpz_t* val) {
    cache[n][v] = val;
}

mpz_t* num(int n, int v) {
    mpz_t* res = get(n, v);
    if (res == NULL) {
        if (n == 0) {
            res = (mpz_t*) malloc(sizeof (mpz_t));
            mpz_init(*res);
        } else if (n == 1) {
            res = (mpz_t*) malloc(sizeof (mpz_t));
            mpz_init(*res);
            mpz_set_si(*res, v);
        } else {
            mpz_t* tmp = (mpz_t*) malloc(sizeof (mpz_t));
            mpz_init_set(*tmp, *(num(n - 1, v + 1)));
            res = tmp;
            int i = 1;
            int j = n - 2;
            for (; j > 0; ++i, --j) {
                mpz_t mul;
                mpz_init(mul);
                mpz_mul(mul, *(num(i, v)), *(num(j, v)));
                mpz_add(*res, *res, mul);
            }
        }
        put(n, v, res);
    }
    return res;
}

int main(int argc, char** argv) {
    map<int, mpz_t*> t = cache[1];
    int i = 0;
    for (; i < 300; ++i) {
        mpz_t * res = num(i, 0);
        gmp_printf("%Zd\n", *res);
    }
    return 0;
}
